package l.l.w.CodingInterviews;

import org.junit.Test;

/**
 * Created by llw on 2018/4/2/0002.
 */
public class 孩子们的游戏 {
    public static void main(String[] args) {
        int i = new 孩子们的游戏().LastRemaining_Solution(3, 2);
        System.out.println(i);
    }
    public int LastRemaining_Solution(int guests, int sec) {
        if(guests < 1 || sec < 1) return -1;
        sec = sec + 1;
        int remain = 0;
        for(int i = 2; i <= guests; ++i){
            remain = (remain + sec) % i;
        }
        return remain;
    }

    @Test
    public void demo1(){
        int[] plants = {3,6,9,8};
        int days = new 孩子们的游戏().removeNeedDays(plants);
        System.out.println(days);
    }

    public int removeNeedDays(int [] plants){
        boolean flag = true;
        int days = 0;
        while(flag){
            int needDelete = 0; //判断是否有需要删除的植物，如果有的话说明循环需要继续，否则可以结束
            int pre = plants[0];
            for(int i = 1; i < plants.length;++i){
                if(plants[i] == -1) continue;
                int temp = plants[i];
                if(temp > pre){
                    plants[i] = -1; //删除植物
                    needDelete++;
                }
                pre = temp;
            }
            if(needDelete > 0) {
                days++;
            }else{
                flag = false;
            }
        }
        return days;
    }
@Test
    public void demo2(){
        int[][] works = new int[4][2];
        works[0] = new int[]{1,2};
        works[1] = new int[]{4,10};
        works[2] = new int[]{20,21};
        works[3] = new int[]{2,23};
        int money = new 孩子们的游戏().getMoney1(4, works);
        System.out.println(money);
    }

    private int money(int days,int[][]works){
        if(days == 0) return works[0][0];
        if(days == 1) {
            int t1 = works[0][0] + works[1][0];
            int t2 = works[1][1];
            return t1 > t2?t1:t2;
        }
        int temp1 = money(days - 1,works);
        int temp2 = money(days - 2, works) + works[days][1];
        return temp1 > temp2 ? temp1 : temp2;
    }
    public int getMoney(int days, int[][] works){
        return money(days-1,works);
    }

    public int getMoney1(int days, int[][] works){
        int [] moneys = new int[days];
        moneys[0] = works[0][0];
        int t1 = moneys[0] + works[1][0];
        int t2 = works[1][1];
        moneys[1] = t1 > t2 ? t1 :t2;
        t1 = moneys[1] + works[2][0];
        t2 = moneys[0] + works[2][1];
        moneys[2] = t1 > t2 ? t1 : t2;
        for(int i = 3; i <days; ++i){
            t1 = moneys[i-1] + works[i][0];
            t2 = moneys[i-2] + works[i][1];
            moneys[i] = t1 > t2 ? t1:t2;
        }
        return  moneys[days-1];
    }

}
